#include <stdio.h>
#include <stdlib.h>
#include "bitree.h"

/*接收值，创建新的结点
 *
 */
void bitree_create(tree_st **ptr,char *a)
{
	while(*a)
	{
		tree_st *newnode = NULL;
		newnode = malloc(sizeof(*newnode));
		if(newnode == NULL)
			return ;
		newnode->data = *a;
		newnode->lchild = NULL;
		newnode->rchild = NULL;
		bitree_insert(ptr,newnode);
		a++;	
	}
}

/*插入新的结点
 *
 *
 */
void bitree_insert(tree_st **ptr,tree_st *newnode)
{
//如果根结点为空，将第一个新节点作为新节点返回	
	if(*ptr == NULL)
	{
		*ptr = newnode;
		return ;
	}
	tree_st *p = *ptr;
	while(p)
	{
//如果新节点大于当前结点，应该接在根的右边		
		if(newnode->data > p->data)
		{
//如果右边结点存在，将p指向此结点，继续进行判断，直到找到叶子结点			
			if(p->rchild)
			{
			p = p->rchild;
			}
			else
			{
				p->rchild = newnode;
				return ;
			}
		}
		else
		{
			if(p->lchild)
			{
			p = p->lchild;
			}
			else
			{
				p->lchild = newnode;
				return ;
			}
		}
	
	}
}

//先序遍历
void bitree_prdisplay(tree_st *ptr)
{
	if(ptr == NULL)
		return;
	printf("%c ",ptr->data);
	bitree_prdisplay(ptr->lchild);
	bitree_prdisplay(ptr->rchild);
}
//中序遍历
void bitree_middisplay(tree_st *ptr)
{
	if(ptr == NULL)
		return;
	bitree_middisplay(ptr->lchild);
	printf("%c ",ptr->data);
	bitree_middisplay(ptr->rchild);

}
//后序遍历
void bitree_postdisplay(tree_st *ptr)
{
	if(ptr == NULL)
		return;
	bitree_postdisplay(ptr->lchild);
	bitree_postdisplay(ptr->rchild);
	printf("%c ",ptr->data);

}

/*删除结点，使树依然有序
 *
 *
 */
tree_st *bitree_delete(tree_st *ptr,Datatype *data)
{
	if(NULL == ptr)
	{
		return NULL;
	}
/*@pr:定义指针pr指向要删除结点的父节点
 *@p:指针p从根结点开始找要删除的结点
 *
 */	
	tree_st *pr = NULL;
	tree_st *p = ptr;
	while(p)
	{
//找到了		
		if(p->data == *data)
		{
			break;
		}
//当前结点的值比要删除的值要大时，往树的左边找，直到找到叶子节点换没找到，证明要找的结点不存在，直接返回		
		else if(p->data > *data)
		{
			if(p->lchild)
			{
				pr = p;
				p = p->lchild;
			}
			else
			{
				return ptr;
			}
		}
//当前结点的值比要删除的值要小时，往树的右边找，直到找到叶子节点换没找到，证明要找的结点不存在，直接返回		
		else
		{
			if(p->rchild)
			{
				pr = p;
				p = p->rchild;
			}
			else
			{
				return ptr;
			}
		}

	}
	
//叶子结点:结点的左右孩子都不存在
delete_start:
	if(NULL == p->lchild && NULL == p->rchild)
	{
//如果要删除的点为根节点，直接释放，返回一个空节点		
		if(p == ptr)
		{
			free(p);
			return NULL;
		}
//如果要删除的结点为父节点的左孩子，将父节点的左孩子置空
		if(pr->lchild == p)
		{
			pr->lchild = NULL;
		}
//如果要删除的结点为父节点的右孩子，将父节点的右孩子置空
		else
		{
			pr->rchild = NULL;
		}
		free(p);
		return ptr;	
	}

//度为1的结点:两种情况	

//结点的左孩子不存在，右孩子存在
	else if(NULL == p->lchild && NULL != p->rchild)
	{
//删除的节点为根节点，将根的右孩子作为新的根结点，将p的右结点置空		
		if(p == ptr)
		{
			ptr = p->rchild;
			p->rchild = NULL;
			free(p);
			return ptr;
		}
//要删除的结点为父节点的左孩子，将右孩子作为新的左孩子，将右孩子置空		
		if(pr->lchild == p)
		{
			pr->lchild = p->rchild;
			p->rchild = NULL;
		}
		else
		{
			pr->rchild = p->rchild;
			p->rchild = NULL;	
		}
		free(p);
		return ptr;
	}
//操作同上	
	else if(NULL != p->lchild && NULL == p->rchild)
	{
		if(p == ptr)
		{
			ptr = p->lchild;
			p->lchild = NULL;
			free(p);
			return ptr;
		}
		
		if(pr->lchild == p)
		{
			pr->lchild = p->lchild;
			p->lchild = NULL;
		}
		else
		{
			pr->rchild = p->lchild;
			p->lchild = NULL;	
		}
		free(p);
		return ptr;
	}
	

//度为2的结点，找到最大的左孩子或者最小的右孩子来顶替
	else
	{
		//用det指向要删除结点的位置
		tree_st *det = p;
		pr = p;
		p = p->lchild;
		while(p->rchild)
		{
			pr = p;
			p = p->rchild;
		}
//将找的的最大值赋值给要删除的结点	
		det->data = p->data;
//删除最大值的那个结点
		goto delete_start;
	}		
	
	

}
